package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月30日
*时间：下午6:40:02
*/
public class Q114 {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    public int uniquePaths(int m, int n) {
        if (n <= 1 || m <= 1) {
            return 1;
        }
        int N = m + n - 2;
        int M = m > n ? n : m;
        return a(N, M - 1);
    }

    private int a(int m, int n) {
        double count = 1;
        while (n >= 1) {
            count = count * (m--) / (n--);
        }
        return (int) Math.round(count);
    }

    @Test
    public void testA() {
        System.out.println(uniquePaths(12, 12));
    }
}
